package com.lwl.Algorithmic_data_structure.class15并查集;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lwl
 * @Description 并查集结构，主要是为了解决一些大数据场景的下容器的合并复杂度过高问题
 * @date 2023/6/1 11:53
 */
public class Code01UnionFind {

    public class Node<V> {

        V value;

        public Node(V value) {
            this.value = value;
        }
    }

    public class UnionFind<V> {

        // 这个map是给调用方使用的，因为调用方处肯定是直接使用原始数据V的，这里需要将其映射到对于的包装类Node
        Map<V, Node> nodeMap;

        // 指向自己的父亲节点
        Map<Node, Node> parentMap;

        // 当前代表节点（根节点）对应的并查集大小
        Map<Node, Integer> sizeMap;

        public UnionFind(List<V> values) {
            nodeMap = new HashMap<>();
            parentMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V value : values) {
                Node<V> node = new Node<>(value);
                nodeMap.put(value, node);
                // 一开始肯定是自己指向自己的
                parentMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        /**
         * 找到自己所在并查集的代表节点，即往上到不能往上的节点
         */
        public Node findFatherNode(V value) {
            Node node = nodeMap.get(value);
            Node t;
            while ((t = parentMap.get(node)) != node) {
                node = t;
            }
            // 这里可以优化为扁平化
            return node;
        }

        /**
         * 是否在同一个并查集下
         */
        public boolean isSameUnionFind(V a, V b) {
            return findFatherNode(a) == findFatherNode(b);
        }

        /**
         * 合并两个并查集
         */
        public void union(V a, V b) {
            Node unionA = findFatherNode(a);
            Node unionB = findFatherNode(b);
            if (unionA != unionB) {
                Integer sizeA = sizeMap.get(unionA);
                Integer sizeB = sizeMap.get(unionB);
                //较小集合连到较大集合下面
                Node<V> big = sizeA >= sizeB ? unionA : unionB;
                Node<V> small = big == unionA ? unionB : unionA;
                parentMap.put(small, big);
                sizeMap.put(big, sizeA + sizeB);
                sizeMap.remove(small);
            }
        }
    }

}
